# 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 
# 
#  此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 
# 
#  
#  
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：nums = [2,0,2,1,1,0]
# 输出：[0,0,1,1,2,2]
#  
# 
#  示例 2： 
# 
#  
# 输入：nums = [2,0,1]
# 输出：[0,1,2]
#  
# 
#  示例 3： 
# 
#  
# 输入：nums = [0]
# 输出：[0]
#  
# 
#  示例 4： 
# 
#  
# 输入：nums = [1]
# 输出：[1]
#  
# 
#  
# 
#  提示： 
# 
#  
#  n == nums.length 
#  1 <= n <= 300 
#  nums[i] 为 0、1 或 2 
#  
# 
#  
# 
#  进阶： 
# 
#  
#  你可以不使用代码库中的排序函数来解决这道题吗？ 
#  你能想出一个仅使用常数空间的一趟扫描算法吗？ 
#  
#  Related Topics 数组 双指针 排序 👍 1108 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        p0, p1 = 0, 0
        for i in range(n):
            if nums[i] == 1:
                nums[i], nums[p1] = nums[p1], nums[i]
                p1 += 1
            if nums[i] == 0:
                nums[i], nums[p0] = nums[p0], nums[i]
                if p0 < p1:
                    nums[i], nums[p1] = nums[p1], nums[i]
                p0 += 1
                p1 += 1


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


"""
单指针, 两次遍历, 一次将0换到头部, 一次将1换到头部(推荐)
"""
"""
双指针1(推荐)
一个指针交换0, 一个指针交换1
找到1, 用p1交换
找到0: 
    先用0指针交换
    如果p0 < p1, 则已经将排好的1换到了后面
    将这个1与p1交换(将1换回到末尾)
    后移p0, p1(p1被p0推后)
ps: 移动p0时, 必定移动p1, 但p1可能自己单独向后走(), 则p1一定大于等于p0

双指针2
一个指针处理0, 一个指针处理2
p1从前向后, p2从后向前
先判断2, 再判断0(如果是0, 继续向前换)
因为从前向后遍历, 后面可能包含未处理的数, p2不一定指向最早的2
所以需要交换2时需要循环交换
"""
#
# class Solution:
#     def sortColors(self, nums: List[int]) -> None:
#         """
#         Do not return anything, modify nums in-place instead.
#         """
#         n = len(nums)
#         p = 0
#         for i in range(n):
#             if nums[i] == 0:
#                 nums[i], nums[p] = nums[p], nums[i]
#                 p += 1
#         for i in range(p, n):
#             if nums[i] == 1:
#                 nums[i], nums[p] = nums[p], nums[i]
#                 p += 1

# def sortColors(self, nums: List[int]) -> None:
#     """
#     Do not return anything, modify nums in-place instead.
#     """
#     n = len(nums)
#     p0, p1 = 0, 0
#     for i in range(n):
#         if nums[i] == 1:
#             nums[i], nums[p1] = nums[p1], nums[i]
#             p1 += 1
#         if nums[i] == 0:
#             nums[i], nums[p0] = nums[p0], nums[i]
#             if p0 < p1:
#                 nums[i], nums[p1] = nums[p1], nums[i]
#             p0 += 1
#             p1 += 1

# def sortColors(self, nums: List[int]) -> None:
#     """
#     Do not return anything, modify nums in-place instead.
#     """
#     n = len(nums)
#     p0, p2 = 0, n - 1
#     i = 0
#     while i <= p2:
#         while i <= p2 and nums[i] == 2:
#             nums[i], nums[p2] = nums[p2], nums[i]
#             p2 -= 1
#         if nums[i] == 0:
#             nums[i], nums[p0] = nums[p0], nums[i]
#             p0 += 1
#         i += 1


# [1, 2, 0]

# [2, 0, 2, 1, 1, 0]
# 0, 2

if __name__ == '__main__':
    s = Solution()
    n1 = [2, 0, 2, 1, 1, 0]
    s.sortColors(n1)
    assert n1 == [0, 0, 1, 1, 2, 2], n1
    n2 = [2, 0, 1]
    s.sortColors(n2)
    assert n2 == [0, 1, 2], n2
    n3 = [1, 2, 0]
    s.sortColors(n3)
    assert n2 == [0, 1, 2], n2
